from collections import defaultdict, Counter


class Solution:
    def balancedString(self, s: str) -> int:
        n = len(s)
        counter = Counter(s)
        target = defaultdict()
        # 筛选覆盖字串
        for key, value in counter.items():
            if value > n // 4:
                target[key] = value - n // 4
        i = 0
        max_length = n
        if target is None: return 0
        for j in range(n):
            # 寻找结束位置
            if s[j] in target:
                target[s[j]] -= 1
            while max(target.values()) <= 0:  # 若都找到了
                max_length = min(max_length, j - i + 1)
                if s[i] in target:
                    target[s[i]] += 1
                i += 1
        return max_length


if __name__ == '__main__':
    s = Solution()
    r = s.balancedString("QWER")
    print(r)
